/**
 * Time some modular exponentiation operations to try to
 * determine why the timing attack in SimpleDemo is not
 * working.
 * 
 * 
 * The Kocher paper modular multiplication times take 
 * 10^-3 s or 1ms, 1000us, 1000000ns
 * 
 * To carry out modular multiplication with 4096-bit 
 * operands and a 4096-bit modulus requires
 * 10^-4 s or 0.1ms, 100us, 100000ns
 * 
 * To carry out modular multiplication with 8192-bit 
 * operands and a 8192-bit modulus requires
 * 4 * 10^-4 s or 0.4ms, 400us, 400000ns
 */
package timingAttack;

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.security.spec.InvalidKeySpecException;

/**
 * @author Vincent
 *
 */
public class TimeModMult 
{

	static final int sampleSize = 1000;
	static final int modulusSize = 16384;
	static final int messageSize = 16383;
	static final String filename = "ModMultTimes." + modulusSize + "." + messageSize + ".txt";

	static final int oneBitDelay = 0;
	
	public static void main(String[] args) throws Exception 
	{
		System.out.println("Generating " + modulusSize + "-bit modulus...");
		BigInteger modulus = BigInteger.ONE;
		try 
		{
			modulus = SimpleDemoVariance.generateModulus(modulusSize);
		} 
		catch (NoSuchAlgorithmException e) 
		{
			e.printStackTrace();
			return;
		} 
		catch (InvalidKeySpecException e) 
		{
			e.printStackTrace();
			return;
		}
		
		System.out.println("\n\nTiming modular exponentiation iterations for zero bits and one bits--should produce positive correlation");
		distinguishBitValues("", sampleSize, messageSize, modulus, 0);

		System.out.println("\n\nTiming vanilla modular multiplication operations--surprisingly uncorrelated");
		simpleModMult("", sampleSize, messageSize, modulus);
	}

	/***
	 * Does a one bit take longer than a zero bit?
	 * 
	 * @param filename		file for writing timing data, "" to skip
	 * @param sampleSize	number of operations to time
	 * @param messageSize	bit size of operands
	 * @param modulus
	 * @param oneBitDelay	artificial delay for one-bits
	 * @throws Exception 
	 */
	static void distinguishBitValues(String filename, int sampleSize, int messageSize, BigInteger modulus, int oneBitDelay) throws Exception
	{
		PrintWriter dst = null;
		if( filename != "" )
		{
			System.out.println("Opening file " + filename);
			try 
			{
				dst = new PrintWriter(new FileWriter(filename));
			} 
			catch(IOException e) 
			{
				System.out.println("Cannot open destination file");
				return;
			}
		}

		SecureRandom r = new SecureRandom();
		
		long [][] time = { new long[sampleSize], new long[sampleSize] };
		BigInteger [] messages = new BigInteger[sampleSize];
		boolean [] bits = new boolean[sampleSize];
		
		System.out.println("Timing " + sampleSize + " modular multiplication operations using " + messageSize + "-bit operands");
	
		for( int i = 0; i < sampleSize; i++ )
		{
			messages[i] = new BigInteger(messageSize,r);
			bits[i] = r.nextBoolean();
			ModExp m = new ModExp(messages[i], modulus, messages[i], new boolean [] { bits[i] }, oneBitDelay );
			time[0][i] = m.time;
			if( i % (sampleSize/20) == 0 ) System.out.print(".");
		}
	
		long [] difference = new long[sampleSize];
		
		// Repeat multiplication operations to see if their execution time is consistent
		for( int i = 0; i < sampleSize; i++ )
		{
			ModExp m = new ModExp(messages[i], modulus, messages[i], new boolean [] { bits[i] }, oneBitDelay );
			time[1][i] = m.time;
			difference[i] = time[0][i] - time[1][i];
			if( filename != "" ) dst.println(time[0][i] + ", " + time[1][i] + ", " + difference[i]);
			if( i % (sampleSize/20) == 0 ) System.out.print(".");
		}

		if( filename != "" )
		{
			System.out.println("Closing file");
			dst.close();
		}
		
		System.out.println("\nMean timing difference: " + Statistics.mean(difference));
		System.out.println("Standard deviation of timing differences: " + Math.sqrt(Statistics.variance(difference)));
		System.out.println("Mean times: " + Statistics.mean(time[0]) + ", " + Statistics.mean(time[1]));
		System.out.println("Standard deviation of times: " + Math.sqrt(Statistics.variance(time[0])) + ", " + Math.sqrt(Statistics.variance(time[1])));
		System.out.println("Correlation between times: " + Statistics.correlation(time[0], time[1]));
	}
	
	/***
	 * Carry out some simple modular multiplication operations
	 * 
	 * @param filename		file for writing timing data, "" to skip
	 * @param sampleSize	number of operations to time
	 * @param messageSize	bit size of operands
	 * @param modulus
	 * @throws Exception 
	 */
	static void simpleModMult(String filename, int sampleSize, int messageSize, BigInteger modulus) throws Exception
	{
		PrintWriter dst = null;
		if( filename != "" )
		{
			System.out.println("Opening file " + filename);
			try 
			{
				dst = new PrintWriter(new FileWriter(filename));
			} 
			catch(IOException e) 
			{
				System.out.println("Cannot open destination file");
				return;
			}
		}

		SecureRandom r = new SecureRandom();
		
		long [][] time = { new long[sampleSize], new long[sampleSize] };
		BigInteger [] messages = new BigInteger[sampleSize];
		
		System.out.println("Timing " + sampleSize + " modular multiplication operations using " + messageSize + "-bit operands");
	
		for( int i = 0; i < sampleSize; i++ )
		{
			messages[i] = new BigInteger(messageSize,r);
			ModExp m = new ModExp(messages[i], modulus, messages[i], new boolean [] { false } );
			time[0][i] = m.time;
			if( i % (sampleSize/20) == 0 ) System.out.print(".");
		}
	
		long [] difference = new long[sampleSize];
		
		// Repeat multiplication operations to see if their execution time is consistent
		for( int i = 0; i < sampleSize; i++ )
		{
			ModExp m = new ModExp(messages[i], modulus, messages[i], new boolean [] { false } );
			time[1][i] = m.time;
			difference[i] = time[0][i] - time[1][i];
			if( filename != "" ) dst.println(time[0][i] + ", " + time[1][i] + ", " + difference[i]);
			if( i % (sampleSize/20) == 0 ) System.out.print(".");
		}

		if( filename != "" )
		{
			System.out.println("Closing file");
			dst.close();
		}
		
		System.out.println("\nMean timing difference: " + Statistics.mean(difference));
		System.out.println("Standard deviation of timing differences: " + Math.sqrt(Statistics.variance(difference)));
		System.out.println("Mean times: " + Statistics.mean(time[0]) + ", " + Statistics.mean(time[1]));
		System.out.println("Standard deviation of times: " + Math.sqrt(Statistics.variance(time[0])) + ", " + Math.sqrt(Statistics.variance(time[1])));
		System.out.println("Correlation between times: " + Statistics.correlation(time[0], time[1]));
	}

}
